1. Field
Various features pertain to wireless communication systems. At least one aspect pertains to methods for generating and/or assigning node identifiers in a peer-to-peer overlay network.
2. Background
Structured peer-to-peer networks use Distributed Hash Tables (DHT) for scalability and deterministic routing of queries. Distributed hash tables (DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a hash table: (node name, identifier value) pairs are stored in the DHT, and any participating node can efficiently retrieve the identifier value associated with a given node name. Each node has a unique identity in the DHT and likewise each service or object stored in the network has a unique identity. All the identities are part of the same identifier space, which is usually very large to avoid collisions. Responsibility for maintaining the identities (e.g., mapping from node names to identifier values ID) is distributed among the nodes, in such a way that a change in the set of participating nodes causes a minimal amount of disruption. This allows DHTs to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures. DHTs form an infrastructure that can be used to build more complex services, such as distributed file systems, peer-to-peer file sharing and content distribution systems, cooperative web caching, multicast, anycast, domain name services, and instant messaging.
However, one weakness is that DHTs have no built-in mechanisms for access control. Any node may obtain multiple IDs (i.e., a Sybil attack where a node may forge multiple identities to subvert the security of a network), join the network in multiple places, and/or disrupt overlay routing, storage and other services. Consequently, malicious nodes may disrupt the efficient operation of DHT network topologies. If the fraction of malicious nodes is f, the probability that a given path in the overlay network is free of malicious nodes is (1f)h, where h is the path length. This decreases rapidly as the path length h increases, even if f (i.e., fraction of malicious nodes) is very small. For example, in a network of 220 nodes (about 1 million nodes), if 3 percent of nodes are malicious, the probability that a given path of 20 hops is free of malicious nodes is about 54 percent.
It is plausible for adversaries to claim ownership of any node ID. Thus node identities must be independently verifiable by an impartial third party.
Additionally, DHTs are also vulnerable to chosen location attacks. Node identities are typically generated as follows: node ID=hash(random-input). An adversary may choose to join a specific region within the overlay network with a small amount of computational work by carefully choosing bits within the input. To join anywhere within a region of size 2x in an overlay network of size 2160, the adversary would perform O(2160-x) offline computations, where O(f(x)) denotes a computation complexity in the order of f(x). Similarly, if uniform placement of nodes within an overlay network is assumed, the offline computational work needs to land between two selected nodes within an overlay network containing 2m nodes is O(2m). In other words, even for a million-node network, the computational work needs to land between two chosen nodes is 220 operations, which is not at all prohibitive. Current assumptions in employing cryptographic measures are to protect against an adversary who can perform O(2128) offline computations and O(280) online computations.
Thus, chosen location attacks are quite feasible. A chosen location allows the adversary to take control over a region between two nodes or a region within the network. The adversary can then disrupt the communications of selected nodes or control access to objects and services that map to the location. In other words, the impact of chosen location attacks is also high. Given the feasibility and potential impact of these attacks, it is imperative that we protect against them.
In chosen location attacks, the adversary carefully selects bits in the random-input to obtain a desired node ID. Thus, the randomness of the input to the hash function must also be verifiable.
Consequently, a method is needed to prevent or minimize adversarial node attacks in an overlay network by safeguarding the node ID generation and/or assignment.